
/*
回溯
连接：https://leetcode.cn/problems/unique-paths-iii/description/
题目：  不同路径 III

算法思路：
对于四个⽅向，我们可以定义⼀个⼆维数组 next ，⼤⼩为 4 ，每⼀维存储四个⽅向的坐标偏移量
（详⻅代码）。题⽬要求到达⽬标位置时所有⽆障碍⽅格都存在路径中，我们可以定义⼀个变量记录
num 当前状态中剩余的未⾛过的⽆障碍⽅格个数，则当我们⾛到⽬标地点时只需要判断 num 是否
为 0 即可。在移动时需要判断是否越界。
递归函数设计：void dfs(vector<vector<int>>& grid, int x, int y, int num)
参数：x，y（当前需要处理元素的坐标），num（当前剩余⽆障碍⽅格个数）；
返回值：⽆；
函数作⽤：判断当前位置的四个⽅向是否可以添加⾄当前状态，查找在满⾜条件下从起始⽅格到结束
⽅格的不同路径的数⽬。
递归流程如下：
1. 递归结束条件：当前位置的元素值为 2，若此时可⾛的位置数量 num 的值为 0，则 cnt 的值加⼀；
2. 遍历四个⽅向，若移动后未越界，⽆障碍并且未被标记，则标记当前位置，并递归移动后的位置，
在回溯时撤销标记操作。

   
    
*/
class Solution {
public:
    bool vis[21][21];
    int m,n;
    int count;
    int uniquePathsIII(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();

        int sum=0;
        int x=0;
        int y =0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==0)
                    sum++;
                if(grid[i][j]==1)
                {
                    x=i;
                    y=j;
                    vis[i][j] = true;
                }
            }
        }
        //sum+1 原因在于第一步走的是1这个数字的坐标，而不是0
        dfs(grid,x,y,sum+1);
        return count;

    }
    int r[4] = {0,0,-1,1};
    int c[4] = {-1,1,0,0};
    void dfs(vector<vector<int>>& grid,int i,int j,int sum)
    {
        if(grid[i][j]==2)
        {
            if(sum==0)
                count++;
            return ;
        }
        for(int k=0;k<4;k++)
        {
            int x = i+r[k];
            int y = j+c[k];
            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && grid[x][y]!=-1)
            {
                vis[x][y] = true;
                dfs(grid,x,y,sum-1);
                vis[x][y] = false;
            }
        }
        return ;
    }
};